package algo.graphe;

import algo.utilitaire.UtilitaireAffichage;
import algo.utilitaire.UtilitaireParcours;
import algo.utilitaire.UtilitaireTas;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.StringTokenizer;

/**
 * Classe Representant un graphe
 *
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christian</a>
 */
public class Graphe {

    /**
     * La matrice d'adjacence du graphe.
     */
    private int[][] matriceAdj;
    /**
     * Determine si le graphe est orienté ou pas
     */
    private boolean oriented;

    /**
     * Retourne une matrice d'adjacence d'un graphe orienté à partir d'un fichier texte
     * @param filename Le fichier où est stocké le graphe
     * @return La matrice d'adjascence
     * @throws IOException
     */
    private int[][] buildMatriceAdjacence(String filename) throws IOException {
        int j;  //  premier sommet
        int k;  //  deuxieme sommet
        int c;  //  cout entre le sommet j et k
        int nodeNumber;
        int[][] matrice;
        BufferedReader input = new BufferedReader(new FileReader(filename));
        String line1 = input.readLine();
        nodeNumber = Integer.parseInt(line1);
        matrice = new int[nodeNumber][nodeNumber];

        while (true) {
            String line = input.readLine();
            if (line == null) {
                break;
            }
            StringTokenizer tok = new StringTokenizer(line, " ");
            j = Integer.parseInt(tok.nextToken());

            //  verification s'il y a encore des tokens
            if (tok.hasMoreTokens()) {
                c = 1;
                k = Integer.parseInt(tok.nextToken());
                //  verification s'il y a encore un token pour le cout du graphe
                if (tok.hasMoreTokens()) {
                    c = Integer.parseInt(tok.nextToken());
                }
                matrice[j][k] = c;
                //  Si le graphe n'est pas orienté on fait aussi dans le sens inverses
                if (!this.oriented) {
                    matrice[k][j] = c;
                }
            }
        }   // while

        return matrice;
    }

    /**
     * Constructeur de la classe Graphe
     * @param filename
     * @param isOriented Determine si le graphe est un graphe orienté ou pas
     */
    public Graphe(String filename, boolean isOriented) {
        this.oriented = isOriented;
        try {
            this.matriceAdj = this.buildMatriceAdjacence(filename);
        } catch (IOException ex) {
            System.err.println("ERREUR Graphe.java contructeur " + ex.getMessage());
        }
    }

    public int[][] getMatriceAdj() {
        return matriceAdj;
    }

    /**
     * Retourne l'ordre du graphe
     * @return 
     */
    public int getOrdre() {
        return this.matriceAdj.length;
    }

    public void setMatriceAdj(int[][] matriceAdj) {
        this.matriceAdj = matriceAdj;
    }

    /**
     * Retourne la valeur matriceAdj[ligne][colonne]
     * @param ligne
     * @param colonne
     * @return
     */
    public int getMatriceAdjValue(int ligne, int colonne) {
        return this.matriceAdj[ligne][colonne];
    }

    public boolean isOriented() {
        return oriented;
    }

    /**
     * Retourne les predecesseurs d'un node dans un graphe.
     * @param node
     * @param matrice
     * @return
     */
    public boolean[] predecesseurs(int node) {
        boolean[] v = new boolean[this.matriceAdj.length];
        for (int i = 0; i < this.matriceAdj.length; i++) {
            v[i] = false;
        }
        for (int i = 0; i < this.matriceAdj.length; i++) {
            if (this.matriceAdj[i][node] > 0) {
                v[i] = true;
            }
        }
        return v;
    }

    /**
     * Verifie si node2 est predecesseur de node1
     * @param node1
     * @param node2
     * @return
     */
    public boolean isPredecesseur(int node1, int node2) {
        //  tout les predecesseurs de node1
        boolean pred[] = this.predecesseurs(node1);
        return (pred[node2]);
    }

    /**
     * Retourne les successeurs d'un sommet
     * @param node LE sommet
     * @return
     */
    public boolean[] successeurs(int node) {
        boolean[] v = new boolean[this.matriceAdj.length];
        for (int i = 0; i < this.matriceAdj.length; i++) {
            v[i] = false;
        }
        for (int i = 0; i < this.matriceAdj.length; i++) {
            if (this.matriceAdj[node][i] != 0) {
                v[i] = true;
            }
        }
        return v;
    }

    public boolean isConnexe() {
        return (this.nbComposantConnexe() == 1);
    }

    /**
     * Retourne le nombre de composant connexe d'un graphe
     * @param matrice
     * @return
     */
    public int nbComposantConnexe() {
        boolean[] visitedTabs = UtilitaireParcours.parcoursLargeur(this, null, 0);
        int nb = 1;

        for (int i = 0; i < visitedTabs.length; i++) {
            if (visitedTabs[i] == false) {
                visitedTabs = UtilitaireParcours.parcoursLargeur(this, visitedTabs, i);
                nb++;
            }
        }
        return nb;
    }

    /**
     * Crée un tableau de noeud qui correspond à la structure de la version 1
     * @return 
     */
    public Noeud[][] creerMatriceTableau() {
        //  colonne getOrdre - 1 car pour un noeud on ne veux pas la valeur de lui même
        Noeud[][] structV1 = new Noeud[this.getOrdre()][this.getOrdre() - 1];
        int c;
        for (int i = 0; i < this.getOrdre(); i++) {
            c = 0;
            for (int j = 0; j < this.getOrdre(); j++) {
                int val = this.getMatriceAdjValue(i, j) == 0 ? Integer.MAX_VALUE : this.getMatriceAdjValue(i, j);
                if (j != i) {
                    structV1[i][c] = new Noeud(j, val);
                    c++;
                }

            }
        }
        return structV1;
    }

    /**
     * Crée un tas à partir de la matrice d'adjacence (structure V2)
     * @return 
     */
    public Noeud[][] creerMatriceTas() {
        //  colonne getOrdre - 1 car pour un noeud on ne veux pas la valeur de lui même
        Noeud[][] structV2 = new Noeud[this.getOrdre()][this.getOrdre() - 1];
        for (int i = 0; i < this.getOrdre(); i++) {
            Noeud[] tas = new Noeud[0];
            for (int j = 0; j < this.getOrdre(); j++) {
                int val = this.getMatriceAdjValue(i, j) == 0 ? Integer.MAX_VALUE : this.getMatriceAdjValue(i, j);
                if (j != i) {
                    tas = UtilitaireTas.ajouter(tas, new Noeud(j, val));
                }
            }
            structV2[i] = tas;
        }
        return structV2;
    }

    /**
     * Créer une liste chainée des distances (structure V3)
     * @return 
     */
    public LinkedList<LinkedList<Noeud>> creerStructureListeChainee() {
        LinkedList<LinkedList<Noeud>> structV3 = new LinkedList<LinkedList<Noeud>>();

        for (int i = 0; i < this.getOrdre(); i++) {
            structV3.add(i, new LinkedList<Noeud>());
            for (int j = 0; j < this.getOrdre(); j++) {
                if (i != j && this.getMatriceAdjValue(i, j) != 0) {
                    structV3.get(i).add(new Noeud(j, this.getMatriceAdjValue(i, j)));
                }
            }
        }

        return structV3;
    }
}